package Offer.q91_minCost;

public class Solution_1 {
    /*
    二维动态规划思路
    首先明确dp[i][j]的意义 我们这里将其设置为将第0 - i号房屋均粉刷完毕 并且第i号房屋刷成第j种颜色 此时的最小花费
    从题中设置的条件 相邻的房屋需要不同颜色 于是可以得出dp[i][j]来自于dp[i - 1][j1] 和 dp[i - 1][j2]
    也就是来自于前一个房屋刷成两种其他颜色的最小值
    出于优化的角度 实际上我们可以复用costs数组 来直接完成动态规划
     */
    public int minCost(int[][] costs) {
        for (int i = 1; i < costs.length; i++) {
            costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
        }
        return Math.min(Math.min(costs[costs.length - 1][0], costs[costs.length - 1][1]), costs[costs.length - 1][2]);
    }
}
